package main.剑指OfferⅠ;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Day20 {
    public static void main(String[] args) {
        System.out.println("剑指Offer07.重建二叉树");
        System.out.println("剑指Offer16.数值的整数次方");
        System.out.println("剑指Offer33.二叉搜索树的后序遍历序列");
    }
}

class Offer07{
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n= preorder.length;
        if (n==0) return null;
        int curVal=preorder[0],rootIndex=0;
        for (int i=0;i<n;i++){
            if (inorder[i]==curVal){
                rootIndex=i;
                break;
            }
        }
        TreeNode root=new TreeNode(curVal);
        root.left=buildTree(Arrays.copyOfRange(preorder,1,1+rootIndex),Arrays.copyOfRange(inorder,0,rootIndex));
        root.right=buildTree(Arrays.copyOfRange(preorder,1+rootIndex,n),Arrays.copyOfRange(inorder,rootIndex+1,n));
        return root;
    }

//    public TreeNode process(List<Integer> lastPre,List<Integer> lastIn){
//        if (lastPre.size()==1) return new TreeNode(lastPre.get(0));//叶节点
//        if (lastPre.size()==0) return null;
//        Integer curVal=lastPre.get(0);//当前节点值
//        TreeNode curNode=new TreeNode(curVal);//当前节点
//        List<Integer> nextLeftPre=new ArrayList<>(),nextLeftIn=new ArrayList<>(),
//                nextRightPre=new ArrayList<>(),nextRightIn=new ArrayList<>();//下一层的先序、中序序列
//        int index=lastIn.indexOf(curVal);//当前节点在中序序列中的位置
//        for (int i=0;i<index;i++) nextLeftIn.add(lastIn.get(i));//获取下层左子树中序序列
//        for (int i=index+1;i<lastIn.size();i++) nextRightIn.add(lastIn.get(i));//获取下层右子树的中序序列
//        for (int i=0;i<lastPre.size();i++){//获取下层左子树先序序列
//            int temp=lastPre.get(i);
//            if (nextLeftIn.contains(temp)) nextLeftPre.add(temp);
//        }
//        for (int i=0;i<lastPre.size();i++){//获取下层右子树先序序列
//            int temp=lastPre.get(i);
//            if (nextRightIn.contains(temp)) nextRightPre.add(temp);
//        }
//        TreeNode left=process(nextLeftPre,nextLeftIn);//构建左子树
//        TreeNode right=process(nextRightPre,nextRightIn);//构建右子树
//        curNode.left=left;
//        curNode.right=right;
//        return curNode;
//    }
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        List<Integer> pre=new ArrayList<>(),in=new ArrayList<>();
//        if (preorder.length==0) return null;
//        for (int num:preorder) pre.add(num);
//        for (int num:inorder) in.add(num);
//        TreeNode result=process(pre,in);
//        return result;
//    }
}

class Offer16{
    double num;
    Map<Integer,Double> dp;
    public double process(int n){
        if (n==1) return num;
        else if (n==2) return (num*num);
        if (dp.containsKey(n)) return dp.get(n);
        else {
            int temp = (int) Math.sqrt(n);
            double result=process(temp)*process(n-temp);
            dp.put(n,result);
            return result;
        }
    }
    public double myPow(double x, int n) {
        this.num=x;
        dp=new HashMap<>();
        if (n==0) return 1.0;
        double result=process(n);
        return result;
    }
}

class Offer33{
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}